The present invention relates to a system and method for forming, storing, and using sets of data values, and more particularly, the present invention relates to a system and method for forming, storing, and using sets of data values as indexes for geographic data so that the amount of space required to store the information content of the data values is reduced.
Some kinds of electronic devices use data stored on a local data storage medium to provide various features and/or functions. In these kinds of electronic devices, the amount of data content that can be stored locally can affect the features and/or functionality provided by the device. Devices of this kind may include portable navigation systems (such as in-vehicle navigation systems), personal digital assistants (such as PalmPilot(copyright)-type devices), portable electronic encyclopedias, portable spell-checkers, etc. For example, portable navigation systems are available that provide end-users (such as drivers of vehicles in which the navigation systems are installed) with various navigating functions and features. Included among the features provided by some navigation systems are route calculation, route guidance, map display, and electronic yellow pages, as well as other features.
In order to provide these and other navigating features and functions, navigation systems use one or more detailed geographic databases. A geographic database includes data that represent physical features in a geographic region. For example, a geographic database used by a navigation system may include data that represents roads and intersections in a geographic region. The geographic data may include information such as the geographic coordinates along road segments, the geographic coordinates of road intersections, turn restrictions at road intersections, speed limits along the roads, street names of the various roads, address ranges along the various roads, and so on. The geographic database may also include other kinds of data. Accordingly, geographic databases used in navigation systems may include a relatively large amount of information and as a consequence geographic databases can be relatively large.
In some navigation systems, some or all the geographic data is stored locally, i.e., on a storage media physically installed with the navigation system. Various kinds of media can be used for storing the geographic database used by a navigation system. Examples of the kinds of media that may be used in navigation systems include CD-ROM disks, PCMCIA cards, and DVD disks. Other kinds of storage media may also be used. Each of these different kinds of storage media has advantages and disadvantages. For example, each of these different types of storage media has a maximum data storage capacity. Thus, for each of these different types of media, there is a maximum amount of data that can be stored on a single unit (e.g., one disk) of the media.
Regardless of the kind of media used for storing geographic data for navigation systems, it is generally desired to be able to store as much data content on the media as possible. Because a media type may have a limited maximum data storage capacity, processes that reduce or minimize the amount of space needed to store a given amount of data content can provide useful advantages. Reducing the amount of space needed to store a given amount of data content allows the saved capacity to be used for the storage of additional geographic data content. For example, the saved capacity can be used to store more details about represented geographic features. Another way that the saved capacity can be used is to increase the size of the coverage area. The coverage area of a geographic database refers to the size of the geographic region represented by the data in the geographic database. A coverage area may include an entire metropolitan area, such as New York and its suburbs, Chicago and its suburbs, or Los Angeles and its suburbs. A coverage area may also include an entire country, such as Germany. In general, it is preferable to make the coverage area as large as possible. Thus, if the amount of space needed to store a given amount of data content can be reduced, the saved capacity can be used to increase the size of the coverage area.
There are conventional data compression techniques that increase the amount of data content that can be stored on a medium. Some conventional data compression techniques have the disadvantage of requiring substantial additional processing to decompress the data from a compressed form in which it is stored on the medium into an uncompressed form that can be used by the software application that uses the data. This additional processing may adversely affect performance of some navigation systems.
Another factor that may limit utilization of conventional data compression techniques for geographic data is that some known data compression techniques may rearrange or replace some or all of the data in order to reduce the amount of space needed to store it on a medium. This kind of rearrangement or replacement may be incompatible or inconsistent with other data arrangements or organizations incorporated in the geographic database that facilitate use of the geographic data by the navigation system. For example, in order to improve navigation system performance generally and in particular to compensate for the limitations of some navigation system platforms that have limited hardware resources, arrangements and organizations can be implemented in a geographic database that facilitate access and use of the data by navigation systems. Since a navigation system uses geographic data in certain known and expected ways to perform known functions, the geographic data can be organized, structured, or arranged in ways that facilitate its use in these known ways by the navigation system. Some of the ways that geographic data can be organized, structured, or arranged to facilitate its access and use by a navigation system are described in EP 0 838 663 published Apr. 24, 1998, the entire disclosure of which is incorporated by reference herein.
As stated above, some conventional data compression techniques involve rearranging portions of the data or replacing portions of an original collection of data with other data. Such data compression techniques may be incompatible with database arrangements and organizations that enhance access and use of geographic data for performing navigation functions. Even if such conventional data compression techniques are not entirely incompatible with the navigation enhancing techniques, they may nonetheless offset the advantages associated with the navigation enhancing techniques.
As explained above, efficient storage of data can provide advantages for portable devices, such as navigation systems, that use data stored locally. Larger, non-portable systems and systems that access data from a remote location may also benefit from efficient storage of data.
Accordingly, it is one objective to provide a means to store data efficiently on a medium. It is another objective to provide a means that stores geographic data efficiently on a medium and that is compatible with organizations and structures incorporated into the geographic database that facilitate its use by a navigation system. It is another objective to provide a data compression technique that can be used for various kinds of data, including geographic data in particular.
To address the above concerns, the present invention comprises a method for storing data efficiently. The method comprises representing a set of actual data values from an original source of data with an alternative representation thereof. One or more parameters of a formula are determined to approximate the set of actual data values in the original source of data. For each actual data value in the original source of data, the difference between the actual data value and the value predicted therefor by the formula is determined. The difference for each actual data value is stored in a data construction on the medium along with the one or more parameters. The alternative representation preserves the information content of the actual data values in the original source of data while reducing the size of the storage requirements for storing the information on a medium.
According to another aspect, the present invention comprises a data construction that stores data efficiently on computer-readable medium. The data construction represents a set of actual data values from an original source of data with an alternative representation thereof. The data construction includes one or more parameters of a formula that approximates the set of actual data values in the original source of data. For each actual data value in the original source of data, the data construction includes a difference, or a representation thereof, between the actual data value and the value predicted therefor by the formula. The alternative representation preserves the information content of the actual data values in the original source of data while reducing the size of the storage requirements for storing the information on a medium.
According still another aspect, the present invention comprises a method for using data stored in a data construction that contains alternative representations of a set of actual data values from an original source of data. The method comprises accessing one or more parameters of a formula that approximates the set of actual data values in the original source of data. The method also includes the step of transforming an alternative representation from the data construction to the actual data value it represents by adding the alternative representation to a value predicted therefor by the formula.